{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Create Sorted Array through Instructions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: createSortedArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过指令创建有序数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>instructions</code> ，你需要根据 <code>instructions</code> 中的元素创建一个有序数组。一开始你有一个空的数组 <code>nums</code> ，你需要 <strong>从左到右</strong> 遍历 <code>instructions</code> 中的元素，将它们依次插入 <code>nums</code> 数组中。每一次插入操作的 <strong>代价</strong> 是以下两者的 <strong>较小值</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums</code> 中 <strong>严格小于 </strong> <code>instructions[i]</code> 的数字数目。</li>\n",
    "\t<li><code>nums</code> 中 <strong>严格大于 </strong> <code>instructions[i]</code> 的数字数目。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，如果要将 <code>3</code> 插入到 <code>nums = [1,2,3,5]</code> ，那么插入操作的 <strong>代价</strong> 为 <code>min(2, 1)</code> (元素 <code>1</code> 和  <code>2</code> 小于 <code>3</code> ，元素 <code>5</code> 大于 <code>3</code> ），插入后 <code>nums</code> 变成 <code>[1,2,3,3,5]</code> 。</p>\n",
    "\n",
    "<p>请你返回将 <code>instructions</code> 中所有元素依次插入 <code>nums</code> 后的 <strong>总最小代价 </strong>。由于答案会很大，请将它对 <code>10<sup>9</sup> + 7</code> <b>取余</b> 后返回。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>instructions = [1,5,6,2]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>一开始 nums = [] 。\n",
    "插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。\n",
    "插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。\n",
    "插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。\n",
    "插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。\n",
    "总代价为 0 + 0 + 0 + 1 = 1 。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>instructions = [1,2,3,6,5,4]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>一开始 nums = [] 。\n",
    "插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。\n",
    "插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。\n",
    "插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。\n",
    "插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。\n",
    "插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。\n",
    "插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。\n",
    "总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>instructions = [1,3,3,3,2,4,2,1,2]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>一开始 nums = [] 。\n",
    "插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。\n",
    "插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。\n",
    "插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。\n",
    "插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。\n",
    "插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。\n",
    "插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。\n",
    "​​​​​插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。\n",
    "插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。\n",
    "插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。\n",
    "总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= instructions.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= instructions[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [create-sorted-array-through-instructions](https://leetcode.cn/problems/create-sorted-array-through-instructions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [create-sorted-array-through-instructions](https://leetcode.cn/problems/create-sorted-array-through-instructions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,6,2]', '[1,2,3,6,5,4]', '[1,3,3,3,2,4,2,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = max(instructions) + 1\n",
    "        tr = [0]*(n + 1)\n",
    "        def add(ind, val):\n",
    "            while ind <= n:\n",
    "                tr[ind] += val\n",
    "                ind += -ind&ind\n",
    "        def query(ind):\n",
    "            res = 0\n",
    "            while ind:\n",
    "                res += tr[ind]\n",
    "                ind -= -ind&ind\n",
    "            return res\n",
    "        def range(left,right):\n",
    "            return query(right) - query(left - 1)\n",
    "\n",
    "        res = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for num in instructions:\n",
    "            l = query(num - 1)\n",
    "            r = range(num + 1, n)\n",
    "            res = (res + min(l, r)) % mod\n",
    "            add(num, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tr = [0]*(n + 1)\n",
    "        self.n = n\n",
    "    def add(self, ind, val):\n",
    "        n = self.n\n",
    "        while ind <= n:\n",
    "            self.tr[ind] += val\n",
    "            ind += -ind&ind\n",
    "    def query(self, ind):\n",
    "        res = 0\n",
    "        while ind:\n",
    "            res += self.tr[ind]\n",
    "            ind -= -ind&ind\n",
    "        return res\n",
    "    def range(self, left,right):\n",
    "        return self.query(right) - self.query(left - 1)\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        n = max(instructions) + 1\n",
    "        tr = BIT(n)\n",
    "        res = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for num in instructions:\n",
    "            l = tr.query(num - 1)\n",
    "            r = tr.range(num + 1, n)\n",
    "            res = (res + min(l, r)) % mod\n",
    "            tr.add(num, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        ans = 0\n",
    "        ordered = list()\n",
    "        for x in instructions:\n",
    "            smaller = bisect.bisect_left(ordered, x)\n",
    "            larger = len(ordered) - bisect.bisect_right(ordered, x)\n",
    "            ans += min(smaller, larger)\n",
    "            ordered[smaller:smaller] = [x]\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        test = []\n",
    "        res = 0\n",
    "        for i in instructions:\n",
    "            left = bisect.bisect_left(test, i)\n",
    "            right = bisect.bisect_right(test, i)\n",
    "            res += min(left, len(test) - right)\n",
    "            insort(test,i)\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\r\n",
    "        def add(x: int) -> None:\r\n",
    "            # 将x插入到树状数组中\r\n",
    "            while x < n:\r\n",
    "                nums[x] += 1\r\n",
    "                x += (x & -x)\r\n",
    "\r\n",
    "        def getSum(x: int) -> int:\r\n",
    "            # 求出小于等于x的元素个数\r\n",
    "            res = 0\r\n",
    "            while x > 0:\r\n",
    "                res += nums[x]\r\n",
    "                x -= (x & -x)\r\n",
    "            return res\r\n",
    "\r\n",
    "        # 创建树状数组\r\n",
    "        n = max(instructions) + 1\r\n",
    "        nums = [0 for _ in range(n)]\r\n",
    "        # res为总代价\r\n",
    "        res = 0\r\n",
    "        # cnt为当前存在元素\r\n",
    "        cnt = 0\r\n",
    "        for i in instructions:\r\n",
    "            # getSum(i-1)求比自己小的元素个数\r\n",
    "            # cnt - getSum(i)求比自己大的元素个数\r\n",
    "            res = (res + min(getSum(i - 1), cnt - getSum(i))) % (10 ** 9 + 7)\r\n",
    "            add(i)\r\n",
    "            cnt += 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        test = []\n",
    "        res = 0\n",
    "        for i in instructions:\n",
    "            left = bisect.bisect_left(test, i)\n",
    "            right = bisect.bisect_right(test, i)\n",
    "            res += min(left, len(test) - right)\n",
    "            test.insert(right, i)\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        ans = 0\n",
    "        ordered = list()\n",
    "        for x in instructions:\n",
    "            smaller = bisect.bisect_left(ordered, x)\n",
    "            larger = len(ordered) - bisect.bisect_right(ordered, x)\n",
    "            ans += min(smaller, larger)\n",
    "            ordered[smaller:smaller] = [x]\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "  def createSortedArray(self, instructions: List[int]) -> int:\n",
    "    bit = BIT(max(instructions))\n",
    "    ans = 0\n",
    "    for i, x in enumerate(instructions):\n",
    "      smaller = bit.query(x - 1)\n",
    "      bigger = i - bit.query(x)\n",
    "      ans += min(smaller, bigger)\n",
    "      bit.update(x)\n",
    "    return ans % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class FenwickTree:\n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.tree = [0] * (size + 1)\n",
    "\n",
    "    def update(self, index, value):\n",
    "        while index <= self.size:\n",
    "            self.tree[index] += value\n",
    "            index += index & -index\n",
    "\n",
    "    def query(self, index):\n",
    "        res = 0\n",
    "        while index:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        max_num = max(instructions)\n",
    "        fenwick = FenwickTree(max_num)\n",
    "\n",
    "        cost = 0\n",
    "        for i, instr in enumerate(instructions):\n",
    "            left = fenwick.query(instr - 1) # numbers < instr\n",
    "            right = i - fenwick.query(instr) # numbers > instr\n",
    "            cost += min(left, right)\n",
    "            fenwick.update(instr, 1)\n",
    "\n",
    "        return cost % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class FenwickTree:\n",
    "    def __init__(self, size: int):\n",
    "        self.size = size\n",
    "        self.tree = [0] * (size + 1)\n",
    "\n",
    "    def update(self, index: int, value: int):\n",
    "        while index <= self.size:\n",
    "            self.tree[index] += value\n",
    "            index += index & -index\n",
    "\n",
    "    def query(self, index: int) -> int:\n",
    "        res = 0\n",
    "        while index:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        maxValue = max(instructions)\n",
    "        fenwick = FenwickTree(maxValue)\n",
    "        cost = 0\n",
    "        n = len(instructions)\n",
    "        \n",
    "        for i, instr in enumerate(instructions):\n",
    "            left = fenwick.query(instr - 1)\n",
    "            right = i - fenwick.query(instr)\n",
    "            cost += min(left, right)\n",
    "            fenwick.update(instr, 1)\n",
    "        \n",
    "        return cost % MOD\n",
    "\n",
    "# 示例使用\n",
    "instructions = [1, 5, 6, 2]\n",
    "sol = Solution()\n",
    "print(sol.createSortedArray(instructions))  # 输出应该是1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 树状数组模板\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    # 将下标 i 上的数加一\n",
    "    def inc(self, i: int) -> None:\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += 1\n",
    "            i += i & -i # add lowbit to right father \n",
    "\n",
    "    # 返回闭区间 [1, i] 的元素和\n",
    "    def sum(self, i: int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.tree[i]\n",
    "            # i &= i - 1\n",
    "            i -= i & -i # minus lowbit to left father\n",
    "        return res\n",
    "\n",
    "    # 返回闭区间 [left, right] 的元素和\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self.sum(right) - self.sum(left - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 单点更新， 区间查询\n",
    "        ans = 0\n",
    "        n = len(instructions)\n",
    "        maxn = max(instructions)\n",
    "        t = BIT(max(instructions) + 1)\n",
    "        for num in instructions:\n",
    "            tmp = min(t.query(1, num - 1), t.query(num + 1, maxn))\n",
    "            ans += tmp\n",
    "            ans %= MOD\n",
    "            t.inc(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x, y):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += y\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        n = max(instructions)\n",
    "        tr = BIT(n + 1)\n",
    "        ans = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for x in instructions:\n",
    "            ans += min(tr.query(x - 1), tr.query(n) - tr.query(x))\n",
    "            \n",
    "            tr.add(x, 1)\n",
    "            #print(x, tr.tree, ans)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        MX = 10**5\n",
    "        tree = [0] * (MX+1)\n",
    "        def lowbit(x):\n",
    "            return x & (-x)\n",
    "        def add(pos,v):\n",
    "            while pos <= MX:\n",
    "                tree[pos]+=v\n",
    "                pos+=lowbit(pos)\n",
    "        def query(pos):\n",
    "            ret = 0\n",
    "            while pos>0:\n",
    "                ret += tree[pos]\n",
    "                pos-=lowbit(pos)\n",
    "            return ret\n",
    "        ans = 0\n",
    "        MOD = 10**9+7\n",
    "        for x in instructions:\n",
    "            \n",
    "            ans = (ans + min(query(x-1), query(MX)-query(x)))%MOD\n",
    "            add(x,1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        test = []\n",
    "        res = 0\n",
    "        for i in instructions:\n",
    "            left = bisect.bisect_left(test, i)\n",
    "            right = bisect.bisect_right(test, i)\n",
    "            res += min(left, len(test) - right)\n",
    "            test.insert(left, i)\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        def add(x: int) -> None:\n",
    "            # 将x插入到树状数组中\n",
    "            while x < n:\n",
    "                nums[x] += 1\n",
    "                x += (x & -x)\n",
    "\n",
    "        def getSum(x: int) -> int:\n",
    "            # 求出小于等于x的元素个数\n",
    "            res = 0\n",
    "            while x > 0:\n",
    "                res += nums[x]\n",
    "                x -= (x & -x)\n",
    "            return res\n",
    "\n",
    "        # 创建树状数组\n",
    "        n = max(instructions) + 1\n",
    "        nums = [0 for _ in range(n)]\n",
    "        # res为总代价\n",
    "        res = 0\n",
    "        # cnt为当前存在元素\n",
    "        cnt = 0\n",
    "        for i in instructions:\n",
    "            # getSum(i-1)求比自己小的元素个数\n",
    "            # cnt - getSum(i)求比自己大的元素个数\n",
    "            res = (res + min(getSum(i - 1), cnt - getSum(i))) % (10 ** 9 + 7)\n",
    "            add(i)\n",
    "            cnt += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "  def createSortedArray(self, instructions: List[int]) -> int:\n",
    "    bit = BIT(max(instructions))\n",
    "    ans = 0\n",
    "    for i, x in enumerate(instructions):\n",
    "      smaller = bit.query(x - 1)\n",
    "      bigger = i - bit.query(x)\n",
    "      ans += min(smaller, bigger)\n",
    "      bit.update(x)\n",
    "    return ans % 1_000_000_007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        ans = 0\n",
    "        lst = SortedList()\n",
    "        for num in instructions:\n",
    "            n = len(lst)\n",
    "            i = lst.bisect_left(num)\n",
    "            j = lst.bisect_right(num)\n",
    "            lst.add(num)\n",
    "            ans += i if i <n - j else n - j\n",
    "            ans %= MOD\n",
    "        return ans\n",
    "\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    # def __init__(self):\n",
    "    #     self.res = 0\n",
    "    #     self.N = 1e10 + 7\n",
    "    #     self.nums = []\n",
    "\n",
    "    # def get_res(self, inputs):\n",
    "    #     key = inputs.pop(0)\n",
    "    #     left, right = 0, len(self.nums)-1\n",
    "    #     mid = (left + right) // 2\n",
    "    #     while right-left>1 and self.nums[mid]!=key:\n",
    "    #         if self.nums[mid] > key:  right = mid\n",
    "    #         else:  left = mid\n",
    "    #         mid = (left + right) // 2\n",
    "    #     if right-left>1:\n",
    "    #         self.res += min(left+1, len(self.nums)-right) % self.N\n",
    "\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        result = 0\n",
    "        pq = SortedList([])\n",
    "        for i in instructions:\n",
    "            nums = len(pq)\n",
    "            result = int( ( result + min(pq.bisect_left(i), nums-pq.bisect_right(i)) ) % (1e9+7) )\n",
    "            pq.add(i)\n",
    "        return result\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        lst = SortedList()\n",
    "        for num in instructions:\n",
    "            small = lst.bisect_left(num)\n",
    "            big = len(lst) - lst.bisect_right(num)\n",
    "            ans += small if small < big else big\n",
    "            lst.add(num)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        res = 0\n",
    "        sl = SortedList()\n",
    "        for num in instructions:\n",
    "            smaller = sl.bisect_left(num)\n",
    "            bigger = len(sl) - sl.bisect_right(num)\n",
    "            res += min(smaller, bigger)\n",
    "            sl.add(num)\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right,bisect_left, insort\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        n = len(instructions)\n",
    "        nums = SortedList()\n",
    "        mod = 10**9 + 7\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            pleft = nums.bisect_left(instructions[i])\n",
    "            pright = nums.bisect_right(instructions[i])\n",
    "            res = (res + min(pleft, i-pright)) % mod\n",
    "            nums.add(instructions[i])\n",
    "        return res % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        l, res = sortedcontainers.SortedList(), 0\n",
    "        for i in instructions:\n",
    "            res += min(l.bisect_left(i), len(l)-l.bisect_right(i))\n",
    "            l.add(i)\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        l, res = sortedcontainers.SortedList(), 0\n",
    "        for i in instructions:\n",
    "            p1 = l.bisect_left(i)\n",
    "            p2 = l.bisect_right(i)\n",
    "            res += min(p1, len(l)-p2)\n",
    "            l.add(i)\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT1:\n",
    "    \"\"\"单点修改\"\"\"\n",
    "\n",
    "    __slots__ = \"size\", \"bit\", \"tree\"\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self.bit = n.bit_length()\n",
    "        self.tree = dict()\n",
    "\n",
    "    def add(self, index: int, delta: int) -> None:\n",
    "        # index 必须大于0\n",
    "        while index <= self.size:\n",
    "            self.tree[index] = self.tree.get(index, 0) + delta\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int: \n",
    "        #外部不要调用，这个不是单点值，是前缀和，查单点值还是用queryRange\n",
    "        if index > self.size:\n",
    "            index = self.size\n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += self.tree.get(index, 0)\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "    def queryRange(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "\n",
    "    def bisectLeft(self, k: int) -> int:\n",
    "        \"\"\"返回第一个前缀和大于等于k的位置pos\n",
    "        1 <= pos <= self.size + 1\n",
    "        \"\"\"\n",
    "        curSum, pos = 0, 0\n",
    "        for i in range(self.bit, -1, -1):\n",
    "            nextPos = pos + (1 << i)\n",
    "            if nextPos <= self.size and curSum + self.tree.get(nextPos, 0) < k:\n",
    "                pos = nextPos\n",
    "                curSum += self.tree.get(pos, 0)\n",
    "        return pos + 1\n",
    "\n",
    "    def bisectRight(self, k: int) -> int:\n",
    "        \"\"\"返回第一个前缀和大于k的位置pos\n",
    "        1 <= pos <= self.size + 1\n",
    "        \"\"\"\n",
    "        curSum, pos = 0, 0\n",
    "        for i in range(self.bit, -1, -1):\n",
    "            nextPos = pos + (1 << i)\n",
    "            if nextPos <= self.size and curSum + self.tree.get(nextPos, 0) <= k:\n",
    "                pos = nextPos\n",
    "                curSum += self.tree.get(pos, 0)\n",
    "        return pos + 1\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        preSum = []\n",
    "        for i in range(self.size):\n",
    "            preSum.append(self.query(i))\n",
    "        return str(preSum)\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self.size\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        res=0\n",
    "        mx=max(instructions)\n",
    "        bit=BIT1(mx+5)\n",
    "        for i in instructions:\n",
    "            if 1<i<mx:\n",
    "                res+=min(bit.queryRange(1,i-1),bit.queryRange(i+1,mx))\n",
    "            res%=mod\n",
    "            bit.add(i,1)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createSortedArray(self, instructions: List[int]) -> int:\n",
    "        m=max(instructions)\n",
    "        d=defaultdict(int)\n",
    "        tree=[0]*(m+1)\n",
    "        def update(x):\n",
    "            while x<=m:\n",
    "                tree[x]+=1\n",
    "                x+=x&(-x)\n",
    "        def query(x):\n",
    "            res=0\n",
    "            while x>0:\n",
    "                res+=tree[x]\n",
    "                x-=x&(-x)\n",
    "            return res\n",
    "        ans=0\n",
    "        for i,x in enumerate(instructions):\n",
    "            a=query(x)\n",
    "            b=d[x]\n",
    "            c=i-a\n",
    "            ans=(ans+min(a-b,c))%1000000007\n",
    "            d[x]+=1\n",
    "            update(x)\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
